/*
 * @Author: 缄默
 * @Date: 2021-12-11 19:08:13
 * @LastEditors: 缄默
 * @LastEditTime: 2021-12-11 19:41:14
 */

//最长公共子串问题

#include <iostream>
#include <vector>
#include <string>

using namespace std;

//空间复杂度o(1)
string getMaxString(string s1, string s2);

//dp解法 空间复杂度o(mn)
vector<vector<int>> getDp(string s1, string s2);

int main() {
    string s1 = "1ab2345cd";
    string s2 = "12345ef";
    cout << getMaxString(s1, s2) << endl;
    
    return 0;
}

string getMaxString(string s1, string s2) {
    //斜线开始位置的行
    int row = 0;
    //斜线开始位置的列
    int col = s2.size() - 1;
    int max = 0;
    int end = 0;
    while (row < s1.size()) {
        int i = row;
        int j = col;
        int len = 0;
        while (i < s1.size() && j < s2.size()) {
            if (s1[i] != s2[j]) {
                len = 0;
            }
            else {
                len++;
            }

            //记录最大值
            if (len > max) {
                end = i;
                max = len;
            }
            i++;
            j++;
        }
        //移动方向
        if (col > 0) {
            col--;
        }
        else {
            row++;
        }
    }
    string res(s1.begin() + end - max + 1, s1.begin() + end + 1);
    return res;
}

vector<vector<int>> getDp(string s1, string s2) {
    vector<vector<int>> dp(s1.size(),vector<int>(s2.size()));
    for (int i = 0; i < s1.size(); i++) {
        dp[i][0] = s1[i] == s2[0] ? 1 : 0;
    }
    for (int i = 0; i < s2.size(); i++) {
        dp[0][i] = s1[0] == s2[i] ? 1 : 0; 
    }
    for (int i = 1; i < s1.size(); i++) {
        for (int j = 1; j < s2.size(); j++) {
            if (s1[i] == s2[j]) {
                dp[i][j] = dp[i - 1][j - 1] + 1;
            }
            else {
                dp[i][j] = 0;
            }
        }
    }
    return dp;
}

